package liecai_class.day01;

import java.util.Arrays;
import java.util.Random;

/**
 * 数组的排序:
 * 3.插入排序
 * - 默认第一位元素已经排好,
 * - 取出第二个元素, 与之前的元素比较, 若前面的元素大于该元素, 将前面的元素向后移动一位
 * - 直到找到比该元素小的元素, 或者比较到第一位为止, 则确定该元素的位置, 并插入该位置
 * - 取出第三个元素, 与之前的元素比较, 若前面的元素大于该元素, 将前面的元素向后移动一位
 * - 直到找到比该元素小的元素, 或者比较到第一位为止, 则确定该元素的位置, 并插入该位置
 * - 重复上述步骤, 直到完成排序
 */
public class ArraySort03 {
    public static void main(String[] args) {
        //生成一个随机数组
        Random rd = new Random();
        int[] arr = new int[10];
        for (int i=0;i<arr.length;i++){
            arr[i] = rd.nextInt(100);
        }
        System.out.println(Arrays.toString(arr));
        /*
            插入排序
         */
        //外层循环, 控制要将哪一个位置的数据进行插入
        for (int i=1;i<arr.length;i++){
            //定义变量, 记录要插入的数据
            int temp = arr[i];
            //内层循环, 从后向前遍历所有已经排好的数据
            //若发现比temp大, 则将其向后移动一位
            //直到发现小于temp或者遍历到首位元素, 则结束循环
            int j=i-1;
            for (;j>=0&&arr[j]>temp;j--){
                //将j位置的数据向后移动一位
                arr[j+1] = arr[j];
            }
            //将temp插入j的位置, 注意上面的循环最后一次j--,
            //所以要将temp赋值给arr[j+1], 完成插入操作
            arr[j+1] = temp;
        }
        System.out.println(Arrays.toString(arr));
    }
}
